#ifndef GRAPH_H
#define GRAPH_H

#include<iostream>
#include<list>
#include<vector>
#include<queue>
#define INF 999999
using namespace std;

/// 顶点类的声明
template<typename T>
class Vertex;
///有向 图类的声明
template<typename T>
class DGraph;
/// 无向图类的声明
template<typename T>
class UdGraph;

/// 边类
template<typename T>
class Edge
{
public:
    Edge()
    {
	from=nullptr;
	to=nullptr;
	weight=1;
    }
    Edge(Vertex<T>& v1,Vertex<T>& v2,int w=1)
    {
	from=&v1;
	to=&v2;
	weight=w;
    }
    ~Edge()
    {
	from=nullptr;
	to=nullptr;
	weight=0;
    }
private:
    /// 两个顶点类的指针，记录边的两个顶点
    Vertex<T> *from;
    Vertex<T> *to;
    int weight;/// 权重，无权默认为1

    friend class DGraph<T>;
    friend class UdGraph<T>;
};

/// 顶点类
template<typename T>
class Vertex
{
public:    
    Vertex(const T& d)
    {
	data=d;
    }
    ~Vertex()
    {
	data=T{};
	adj.clear();
	distance=0;
    }
    /// 重载了＝＝符号
    bool operator==(Vertex<T> v0)
    {
	return this->data==v0.data;
    }

private:
    T data;/// 顶点存放的数据
    list<Edge<T>> adj;/// 顶点的邻接表，存放相关的边
    int distance;
    int isinqueue;

    friend class DGraph<T>;
    friend class UdGraph<T>;
};

/// 图抽象类
template<typename T>
class Graph
{
public:
    virtual void insertVertex(const T& d)=0;   
    virtual void deleteVertex(const T& d)=0;
    virtual void insertEdge(const T& d1,const T& d2,int w=0)=0;
    virtual void deleteEdge(const T& d1,const T& d2)=0;
};

/// 有向图类
template<typename T>
class DGraph:public Graph<T>
{
private:
    int numVertex;/// 记录图的顶点数量
    int storagemode;/// 图的存储模式，0代表邻接表，1代表邻接矩阵
    vector<Vertex<T>> VertexTable;/// 存放图中的顶点
    vector<vector<int>> EdgeMatrix;/// 邻接矩阵
public:
    /// 用户直接指定存储方式
    DGraph(int mode=0)
    {
	numVertex=0;
	storagemode=mode;
    }
    /// 用户输入图可能的最大顶点数和边数，根据数量关系决定图的存储模式
    DGraph(int MaxVertexnum,int MaxEdgenum)
    {
	numVertex=0;
	/// 当最大边数接近最大顶点数的平方时选择邻接矩阵存储方式
	if(MaxEdgenum>=MaxVertexnum*MaxVertexnum-2*MaxVertexnum)
	{
	    storagemode=1;
	}
	/// 否则选择邻接表存储
	else
	{
	    storagemode=0;
	}
    }
    ~DGraph()
    {
	numVertex=0;
	VertexTable.clear();
	EdgeMatrix.clear();
    }

    /// 循环遍历列出图中所有顶点
    void listVertexes()const
    {
	for(typename vector<Vertex<T>>::const_iterator itr=VertexTable.begin();itr!=VertexTable.end();++itr)
	{
	    cout<<(*itr).data<<" ";
	}
	cout<<endl;
	return;
    }
    /// 循环遍历列出图中所有边
    void listEdges()const
    {
	if(storagemode==0)
	{
	    for(typename vector<Vertex<T>>::const_iterator itr1=VertexTable.begin();itr1!=VertexTable.end();++itr1)
	    {
		for(typename list<Edge<T>>::const_iterator itr2=(*itr1).adj.begin();itr2!=(*itr1).adj.end();++itr2)
		{
		    cout<<"("<<(*(*itr2).from).data<<","<<(*(*itr2).to).data<<","<<(*itr2).weight<<") ";
		}
	    }
	    cout<<endl;
	    return;
	}
	else
	{
	    for(int i=0;i<numVertex;i++)
	    {
		for(int j=0;j<numVertex;j++)
		{
		    if(EdgeMatrix[i][j])/// 存储0表示边不存在
		    {
			cout<<"("<<VertexTable[i].data<<","<<VertexTable[j].data<<","<<EdgeMatrix[i][j]<<") ";
		    }
		}
	    }
	    cout<<endl;
	    return;
	}
    }
    /// 判断对应顶点是否存在
    bool containVertex(const T& d)const
    {
	for(typename vector<Vertex<T>>::const_iterator itr=VertexTable.begin();itr!=VertexTable.end();++itr)
	{
	    if((*itr).data==d)
	    {
		return true;
	    }
	}
	/// 若顶点不存在则返回假
	return false;
    }
    /// 插入顶点
    void insertVertex(const T& d)
    {
	/// 若顶点已存在则中止函数
	if(containVertex(d))
	{
	    cout<<"vertex has existed"<<endl;
	    return;
	}
	Vertex<T> v(d);
	VertexTable.push_back(v);
	numVertex++;
	if(storagemode!=0)
	{
	    /// 维护邻接矩阵，用0来扩充矩阵
	    vector<int> e(numVertex);
	    EdgeMatrix.push_back(e);
	    for(int i=0;i<numVertex-1;i++)
	    {
		EdgeMatrix[i].push_back(0);
	    }
	}
    }
    /// 删除顶点
    void deleteVertex(const T& d)
    {
	/// 状态变量，1代表顶点不存在，0则反之
	int flag=1;
	if(storagemode==0)
	{
	    for(typename vector<Vertex<T>>::iterator itr1=VertexTable.begin();itr1!=VertexTable.end();)
	    {
		if((*itr1).data==d)
		{
		    VertexTable.erase(itr1);/// 删除顶点
		    numVertex--; 
		    flag=0;/// 0代表找到顶点
		    if(itr1==VertexTable.end())
		    {
			break;
		    }
		}
		else
		{
		    /// 删除所有与该顶点相关的边
		    for(typename list<Edge<T>>::iterator itr2=(*itr1).adj.begin();itr2!=(*itr1).adj.end();++itr2)
		    {
			if((*(*itr2).to).data==d)
			{
			    (*itr1).adj.erase(itr2);
			    break;
			}
		    }
		    ++itr1;
		}
	    }
	    /// 若顶点不存在则中止函数
	    if(flag)
	    {
		cout<<"vertex not exist"<<endl;
		return;
	    }
	}
	else
	{
	    /// 位置变量，记录目标顶点位置
	    int p=0;
	    /// 邻接矩阵迭代器，记录要删除的边所在行对应位置
	    typename vector<vector<int>>::iterator itr2=EdgeMatrix.begin();
	    for(typename vector<Vertex<T>>::iterator itr1=VertexTable.begin();itr1!=VertexTable.end();++itr1,++itr2)
	    {
		if((*itr1).data==d)
		{
		    VertexTable.erase(itr1);
		    numVertex--;
		    /// 删除顶点在邻接矩阵对应的行
		    EdgeMatrix.erase(itr2);
		    flag=0;
		    break;
		}
		p++;
	    }
	    /// 若顶点不存在则中止函数
	    if(flag)
	    {
		cout<<"vertex not exist"<<endl;
		return;
	    }
	    /// 循环删除顶点在邻接矩阵对应的列
	    for(typename vector<vector<int>>::iterator itr3=EdgeMatrix.begin();itr3!=EdgeMatrix.end();++itr3)
	    {
		vector<int>::iterator itr4=(*itr3).begin();
		for(int i=0;i<p;i++)
		{
		    itr4++;
		}
		(*itr3).erase(itr4);
	    }
	}
	return;
    }
    /// 判断对应边是否存在
    bool containEdge(const T& d1,const T& d2)const
    {
	/// 位置变量，分别记录两个顶点位置
	int u=-1,v=-1,i=0;
	for(typename vector<Vertex<T>>::const_iterator itr=VertexTable.begin();itr!=VertexTable.end();++itr,i++)
	{
	    if((*itr).data==d1)
	    {
		u=i;
	    }
	    if((*itr).data==d2)
	    {
		v=i;
	    }
	}
	/// 若顶点不存在则边不存在返回假
	if(u==-1||v==-1)
	{	    
	    return false;
	}
	if(storagemode==0)
	{
	    for(typename list<Edge<T>>::const_iterator itr=VertexTable[u].adj.begin();itr!=VertexTable[u].adj.end();++itr)
	    {
		if((*(*itr).to).data==d2)
		{
		    return true;
		}
	    }
	    return false;
	}
	else
	{
	    /// 若边不存在则返回假
	    if(EdgeMatrix[u][v]==0)
	    {
		return false;
	    }
	    return true;
	}
    }
    /// 插入边
    void insertEdge(const T& d1,const T& d2,int w=1)
    {
	/// 位置变量，分别记录两个顶点位置
	int u=-1,v=-1,i=0;
	for(typename vector<Vertex<T>>::iterator itr=VertexTable.begin();itr!=VertexTable.end();++itr,i++)
	{
	    if((*itr).data==d1)
	    {
		u=i;
	    }
	    if((*itr).data==d2)
	    {
		v=i;
	    }
	}
	/// 若位置变量仍为-1则顶点不存在
	if(u==-1||v==-1)
	{
	    cout<<"vertex not exist"<<endl;
	    return;
	}
	if(storagemode==0)
	{
	    /// 遍历第一个顶点的邻接表，若边已存在则中止函数
	    for(typename list<Edge<T>>::const_iterator itr=VertexTable[u].adj.begin();itr!=VertexTable[u].adj.end();++itr)
	    {
		if((*(*itr).to).data==d2)
		{
		    cout<<"edge has existed"<<endl;
		    return;
		}
	    }
	    /// 对应顶点的邻接表中存放边
	    Edge<T> e(VertexTable[u],VertexTable[v],w);
	    VertexTable[u].adj.push_back(e);
	}
	else
	{
	    /// 若边已存在则中止函数
	    if(EdgeMatrix[u][v])
	    {
		cout<<"edge has existed"<<endl;
		return;
	    }
	    /// 邻接矩阵中存放权重
	    EdgeMatrix[u][v]=w;
	}
	return;
    }
    /// 删除边
    void deleteEdge(const T& d1,const T& d2)
    {
	/// 位置变量，分别记录两个顶点位置
	int u=-1,v=-1,i=0;
	for(typename vector<Vertex<T>>::iterator itr=VertexTable.begin();itr!=VertexTable.end();++itr,i++)
	{
	    if((*itr).data==d1)
	    {
		u=i;
	    }
	    if((*itr).data==d2)
	    {
		v=i;
	    }
	}
	/// 若顶点不存在则中止函数
	if(u==-1||v==-1)
	{
	    cout<<"vertex not exist"<<endl;
	    return;
	}
	if(storagemode==0)
	{
	    for(typename list<Edge<T>>::iterator itr=VertexTable[u].adj.begin();itr!=VertexTable[u].adj.end();++itr)
	    {
		if((*(*itr).to).data==d2)
		{
		    VertexTable[u].adj.erase(itr);
		    return;
		}
	    }
	    /// 若边不存在则中止函数
	    cout<<"edge not exist"<<endl;
	    return;
	}
	else
	{
	    /// 若边不存在则中止函数
	    if(EdgeMatrix[u][v]==0)
	    {
		cout<<"edge not exist"<<endl;
		return;
	    }
	    /// 邻接矩阵存储0代表边不存在
	    EdgeMatrix[u][v]=0;
	    return;
	}
    }

    void BellmanFord(const T& d)
    {
	int flag=1;
        for(typename vector<Vertex<T>>::iterator itr=VertexTable.begin();itr!=VertexTable.end();++itr)
	{
	    if((*itr).data==d)
	    {
		(*itr).distance=0;
		flag=0;
	    }
	    else
	    {
		(*itr).distance=INF;
	    }
	}
	/// 若顶点不存在则中止函数
        if(flag)
	{
	    cout<<"vertex not exist"<<endl;
	    return;
	}	
	if(storagemode==0)
	{
	    for(int k=1;k<numVertex;k++)
	    {
		for(typename vector<Vertex<T>>::iterator itr1=VertexTable.begin();itr1!=VertexTable.end();++itr1)
		{
		    for(typename list<Edge<T>>::iterator itr2=(*itr1).adj.begin();itr2!=(*itr1).adj.end();++itr2)
		    {
			if((*(*itr2).to).distance>(*(*itr2).from).distance+(*itr2).weight)
			{
			    (*(*itr2).to).distance=(*(*itr2).from).distance+(*itr2).weight;
			}
		    }
		}		
	    }
	    /// 检查负权回路
	    for(typename vector<Vertex<T>>::iterator itr1=VertexTable.begin();itr1!=VertexTable.end();++itr1)
	    {
		for(typename list<Edge<T>>::iterator itr2=(*itr1).adj.begin();itr2!=(*itr1).adj.end();++itr2)
		{
		    if((*(*itr2).to).distance>(*(*itr2).from).distance+(*itr2).weight)
		    {
			cout<<"negative-cost cycle exist"<<endl;
			return;
		    }
		}
	    }
	}
	else
	{
	    for(int k=1;k<numVertex;k++)
	    {
		for(int i=0;i<numVertex;i++)
		{
		    for(int j=0;j<numVertex;j++)
		    {
			if(EdgeMatrix[i][j])/// 存储0表示边不存在
			{
			    if(VertexTable[j].distance>VertexTable[i].distance+EdgeMatrix[i][j])
			    {
				VertexTable[j].distance=VertexTable[i].distance+EdgeMatrix[i][j];
			    }
			}
		    }
		}
	    }
	     /// 检查负权回路
	    for(int i=0;i<numVertex;i++)
	    {
		for(int j=0;j<numVertex;j++)
		{
		    if(EdgeMatrix[i][j])/// 存储0表示边不存在
		    {
			if(VertexTable[j].distance>VertexTable[i].distance+EdgeMatrix[i][j])
			{
			    cout<<"negative-cost cycle exist"<<endl;
			    return;
			}
		    }
		}
	    }
	}
	/// 输出结果
	for(typename vector<Vertex<T>>::iterator itr=VertexTable.begin();itr!=VertexTable.end();++itr)
	{
	    cout<<"["<<(*itr).data<<","<<(*itr).distance<<"] ";
	}
	cout<<endl;
	return;
    }

    /// 队列优化的bellmanford算法，尽量避免n-1次的冗余循环
    void superBellmanFord(const T& d)
    {
	int flag=1;
	queue<Vertex<T>*> q;
        for(typename vector<Vertex<T>>::iterator itr=VertexTable.begin();itr!=VertexTable.end();++itr)
	{
	    if((*itr).data==d)
	    {
		(*itr).distance=0;
		flag=0;
		q.push(&(*itr));
		(*itr).isinqueue=1;
	    }
	    else
	    {
		(*itr).distance=INF;
		(*itr).isinqueue=0;
	    }
	}
	/// 若顶点不存在则中止函数
        if(flag)
	{
	    cout<<"vertex not exist"<<endl;
	    return;
	}	
	if(storagemode==0)
	{
	    while(!q.empty())
	    {
		for(typename list<Edge<T>>::iterator itr=(*q.front()).adj.begin();itr!=(*q.front()).adj.end();++itr)
		{
		    if((*(*itr).to).distance>(*(*itr).from).distance+(*itr).weight)
		    {
			(*(*itr).to).distance=(*(*itr).from).distance+(*itr).weight;
			if((*(*itr).to).isinqueue==0)
			{
			    q.push((*itr).to);
			    (*(*itr).to).isinqueue=1;
			}
		    }
		}
		(*q.front()).isinqueue=0;
		q.pop();
	    }
	    /// 检查负权回路
	    for(typename vector<Vertex<T>>::iterator itr1=VertexTable.begin();itr1!=VertexTable.end();++itr1)
	    {
	    	for(typename list<Edge<T>>::iterator itr2=(*itr1).adj.begin();itr2!=(*itr1).adj.end();++itr2)
	    	{
	    	    if((*(*itr2).to).distance>(*(*itr2).from).distance+(*itr2).weight)
	    	    {
	    		cout<<"negative-cost cycle exist"<<endl;
	    		return;
	    	    }
	    	}
	    }
	}
	else
	{
	    while(!q.empty())
	    {
		int i;
		for(i=0;i<numVertex;i++)
		{
		    if(VertexTable[i]==(*q.front()))
		    {
			break;
		    }
		}
		for(int j=0;j<numVertex;j++)
		{
		    if(EdgeMatrix[i][j])/// 存储0表示边不存在
		    {
			if(VertexTable[j].distance>VertexTable[i].distance+EdgeMatrix[i][j])
			{
			    VertexTable[j].distance=VertexTable[i].distance+EdgeMatrix[i][j];
			    if(VertexTable[j].isinqueue==0)
			    {
				q.push(&VertexTable[j]);
				VertexTable[j].isinqueue=1;
			    }
			}
		    }
		}
		(*q.front()).isinqueue=0;
		q.pop();
	    }
	     /// 检查负权回路
	    for(int i=0;i<numVertex;i++)
	    {
		for(int j=0;j<numVertex;j++)
		{
		    if(EdgeMatrix[i][j])/// 存储0表示边不存在
		    {
			if(VertexTable[j].distance>VertexTable[i].distance+EdgeMatrix[i][j])
			{
			    cout<<"negative-cost cycle exist"<<endl;
			    return;
			}
		    }
		}
	    }
	}
	/// 输出结果
	for(typename vector<Vertex<T>>::iterator itr=VertexTable.begin();itr!=VertexTable.end();++itr)
	{
	    cout<<"["<<(*itr).data<<","<<(*itr).distance<<"] ";
	}
	cout<<endl;
	return;
    }
};


/// 无向图类
template<typename T>
class UdGraph:public Graph<T>
{
private:
    int numVertex;/// 记录图的顶点数量
    int storagemode;/// 图的存储模式，0代表邻接表，1代表邻接矩阵
    vector<Vertex<T>> VertexTable;/// 存放图中的顶点
    vector<vector<int>> EdgeMatrix;/// 邻接矩阵
public:
    UdGraph(int mode=0)
    {
	numVertex=0;
	storagemode=mode;
    }
    /// 用户输入图可能的最大顶点数和边数，根据数量关系决定图的存储模式
    UdGraph(int MaxVertexnum,int MaxEdgenum)
    {
	numVertex=0;
	/// 当最大边数接近最大顶点数的平方时选择邻接矩阵存储方式
	if(2*MaxEdgenum>=MaxVertexnum*MaxVertexnum-2*MaxVertexnum)
	{
	    storagemode=1;
	}
	/// 否则选择邻接表存储
	else
	{
	    storagemode=0;
	}
    }
    ~UdGraph()
    {
	numVertex=0;
	VertexTable.clear();
	EdgeMatrix.clear();
    }

    /// 循环遍历列出图中所有顶点
    void listVertexes()const
    {
	for(typename vector<Vertex<T>>::const_iterator itr=VertexTable.begin();itr!=VertexTable.end();++itr)
	{
	    cout<<(*itr).data<<" ";
	}
	cout<<endl;
	return;
    }
    /// 循环遍历列出图中所有边
    void listEdges()const
    {
	if(storagemode==0)
	{
	    for(typename vector<Vertex<T>>::const_iterator itr1=VertexTable.begin();itr1!=VertexTable.end();++itr1)
	    {
		for(typename list<Edge<T>>::const_iterator itr2=(*itr1).adj.begin();itr2!=(*itr1).adj.end();++itr2)
		{
		    /// 避免无向图重复输出边
		    if((*itr1).data==(*(*itr2).from).data)
		    {
			cout<<"("<<(*(*itr2).from).data<<","<<(*(*itr2).to).data<<","<<(*itr2).weight<<") ";
		    }
		}
	    }
	    cout<<endl;
	    return;
	}
	else
	{
	    for(int i=0;i<numVertex;i++)
	    {
		/// 无向图的邻接矩阵是对称阵
		for(int j=0;j<=i;j++)
		{
		    if(EdgeMatrix[i][j])/// 存储0表示边不存在
		    {
			cout<<"("<<VertexTable[i].data<<","<<VertexTable[j].data<<","<<EdgeMatrix[i][j]<<") ";
		    }
		}
	    }
	    cout<<endl;
	    return;
	}
    }
     /// 判断对应顶点是否存在
    bool containVertex(const T& d)const
    {
	for(typename vector<Vertex<T>>::const_iterator itr=VertexTable.begin();itr!=VertexTable.end();++itr)
	{
	    if((*itr).data==d)
	    {
		return true;
	    }
	}
	/// 若顶点不存在则返回假
	return false;
    }
    /// 插入顶点
    void insertVertex(const T& d)
    {
	/// 若顶点已存在则中止函数
	if(containVertex(d))
	{
	    cout<<"vertex has existed"<<endl;
	    return;
	}
	Vertex<T> v(d);
	VertexTable.push_back(v);
	numVertex++;
	if(storagemode!=0)
	{
	    /// 维护邻接矩阵，用0来扩充矩阵
	    vector<int> e(numVertex);
	    EdgeMatrix.push_back(e);
	    for(int i=0;i<numVertex-1;i++)
	    {
		EdgeMatrix[i].push_back(0);
	    }
	}
    }
    /// 删除顶点
    void deleteVertex(const T& d)
    {
	/// 状态变量，1代表顶点不存在，0则反之
	int flag=1;
	if(storagemode==0)
	{
	    for(typename vector<Vertex<T>>::iterator itr1=VertexTable.begin();itr1!=VertexTable.end();)
	    {
		if((*itr1).data==d)
		{
		    VertexTable.erase(itr1);/// 删除顶点
		    numVertex--; 
		    flag=0;/// 0代表找到顶点
		    if(itr1==VertexTable.end())
		    {
			break;
		    }
		}
		else
		{
		    /// 删除所有与该顶点相关的边
		    for(typename list<Edge<T>>::iterator itr2=(*itr1).adj.begin();itr2!=(*itr1).adj.end();++itr2)
		    {
			if((*(*itr2).to).data==d||(*(*itr2).from).data==d)
			{
			    (*itr1).adj.erase(itr2);
			    break;
			}
		    }
		    ++itr1;
		}
	    }
	    /// 若顶点不存在则中止函数
	    if(flag)
	    {
		cout<<"vertex not exist"<<endl;
		return;
	    }
	}
	else
	{
	    /// 位置变量，记录目标顶点位置
	    int p=0;
	    /// 邻接矩阵迭代器，记录要删除的边所在行对应位置
	    typename vector<vector<int>>::iterator itr2=EdgeMatrix.begin();
	    for(typename vector<Vertex<T>>::iterator itr1=VertexTable.begin();itr1!=VertexTable.end();++itr1,++itr2)
	    {
		if((*itr1).data==d)
		{
		    VertexTable.erase(itr1);
		    numVertex--;
		    /// 删除顶点在邻接矩阵对应的行
		    EdgeMatrix.erase(itr2);
		    flag=0;
		    break;
		}
		p++;
	    }
	    /// 若顶点不存在则中止函数
	    if(flag)
	    {
		cout<<"vertex not exist"<<endl;
		return;
	    }
	    /// 循环删除顶点在邻接矩阵对应的列
	    for(typename vector<vector<int>>::iterator itr3=EdgeMatrix.begin();itr3!=EdgeMatrix.end();++itr3)
	    {
		typename vector<int>::iterator itr4=(*itr3).begin();
		for(int i=0;i<p;i++)
		{
		    itr4++;
		}
		(*itr3).erase(itr4);
	    }
	}
	return;
    }
    /// 判断对应边是否存在
    bool containEdge(const T& d1,const T& d2)const
    {
	/// 位置变量，分别记录两个顶点位置
	int u=-1,v=-1,i=0;
	for(typename vector<Vertex<T>>::const_iterator itr=VertexTable.begin();itr!=VertexTable.end();++itr,i++)
	{
	    if((*itr).data==d1)
	    {
		u=i;
	    }
	    if((*itr).data==d2)
	    {
		v=i;
	    }
	}
	/// 若顶点不存在则边不存在返回假
	if(u==-1||v==-1)
	{	    
	    return false;
	}
	if(storagemode==0)
	{
	    for(typename list<Edge<T>>::const_iterator itr=VertexTable[u].adj.begin();itr!=VertexTable[u].adj.end();++itr)
	    {
		if((*(*itr).to).data==d2||(*(*itr).from).data==d2)
		{
		    return true;
		}
	    }
	    return false;
	}
	else
	{
	    /// 若边不存在则返回假
	    if(EdgeMatrix[u][v]==0)
	    {
		return false;
	    }
	    return true;
	}
    }
    /// 插入边
    void insertEdge(const T& d1,const T& d2,int w=1)
    {
	/// 位置变量，分别记录两个顶点位置
	int u=-1,v=-1,i=0;
	for(typename vector<Vertex<T>>::iterator itr=VertexTable.begin();itr!=VertexTable.end();++itr,i++)
	{
	    if((*itr).data==d1)
	    {
		u=i;
	    }
	    if((*itr).data==d2)
	    {
		v=i;
	    }
	}
	/// 若位置变量仍为-1则顶点不存在
	if(u==-1||v==-1)
	{
	    cout<<"vertex not exist"<<endl;
	    return;
	}
	if(storagemode==0)
	{
	    /// 遍历第一个顶点的邻接表，若边已存在则中止函数
	    for(typename list<Edge<T>>::iterator itr=VertexTable[u].adj.begin();itr!=VertexTable[u].adj.end();++itr)
	    {
		if((*(*itr).to).data==d2||(*(*itr).from).data==d2)
		{
		    cout<<"edge has existed"<<endl;
		    return;
		}
	    }
	    /// 对应顶点的邻接表中存放边
	    Edge<T> e(VertexTable[u],VertexTable[v],w);
	    VertexTable[u].adj.push_back(e);
	    VertexTable[v].adj.push_back(e);
	}
	else
	{
	    /// 若边已存在则中止函数
	    if(EdgeMatrix[u][v])
	    {
		cout<<"edge has existed"<<endl;
		return;
	    }
	    /// 邻接矩阵中存放权重
	    EdgeMatrix[u][v]=w;
	    EdgeMatrix[v][u]=w;
	}
	return;
    }
    /// 删除边
    void deleteEdge(const T& d1,const T& d2)
    {
	/// 位置变量，分别记录两个顶点位置
	int u=-1,v=-1,i=0;
	for(typename vector<Vertex<T>>::iterator itr=VertexTable.begin();itr!=VertexTable.end();++itr,i++)
	{
	    if((*itr).data==d1)
	    {
		u=i;
	    }
	    if((*itr).data==d2)
	    {
		v=i;
	    }
	}
	/// 若顶点不存在则中止函数
	if(u==-1||v==-1)
	{
	    cout<<"vertex not exist"<<endl;
	    return;
	}
	if(storagemode==0)
	{
	    int flag=1;
	    for(typename list<Edge<T>>::iterator itr1=VertexTable[u].adj.begin();itr1!=VertexTable[u].adj.end();++itr1)
	    {
		if((*(*itr1).to).data==d2||(*(*itr1).from).data==d2)
		{
		    VertexTable[u].adj.erase(itr1);
		    flag=0;
		    break;
		}
	    }
	    for(typename list<Edge<T>>::iterator itr2=VertexTable[v].adj.begin();itr2!=VertexTable[v].adj.end();++itr2)
	    {
		if((*(*itr2).from).data==d1||(*(*itr2).to).data==d1)
		{
		    VertexTable[v].adj.erase(itr2);
		    flag=0;
		    break;
		}
	    }
	    /// 若边不存在则中止函数
	    if(flag)
	    {
		cout<<"edge not exist"<<endl;
		return;
	    }
	    return;
	}
	else
	{
	    /// 若边不存在则中止函数
	    if(EdgeMatrix[u][v]==0)
	    {
		cout<<"edge not exist"<<endl;
		return;
	    }
	    /// 邻接矩阵存储0代表边不存在
	    EdgeMatrix[u][v]=0;
	    EdgeMatrix[v][u]=0;
	    return;
	}
    }
};

#endif
